
// 33.搜索旋转排序数组
class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 先找最小值
        int n = nums.size();
        int left = -1 , right = n -1;
        while(left + 1 < right)
        {
            int mid = left + (right - left)/2;
            if(nums[mid] > nums[right]) left = mid;
            else right = mid;
        } 
        // 此时nums[right]是最小值
        // 根据target判断从那边进行二分
        int l = right , r =  n;
        if(nums[r - 1] < target) 
            l = 0 , r = right;

        int pos = lower_bound(nums.begin() + l , nums.begin() + r ,target) - nums.begin();
        return nums[pos] == target ? pos : -1;
    }
};